module(..., package.seeall) 

gr = require "graphs" 
q = require "queues" 
st = require "stacks"


function bfs(g,s) 
   local bfs_results = {} 
   local bfs_q = q.new() 

   local function step()
      local u = q.dequeue(bfs_q) 
      if u 
      then 
	 for _,e in pairs(g[u]) do 
	    local v = e.dst
	    if not(bfs_results[v]) 
	    then 
	       bfs_results[v] = {d = (bfs_results[u].d)+1, 
				 pi = u}
	       q.enqueue(bfs_q,v)
	    end
	 end
	 step() 
      else 
	 return bfs_results 
      end
   end

   bfs_results[s] = {d = 0} 
   q.enqueue(bfs_q,s) 
   step() 
   return bfs_results
end

function print_bfs_results(g,r) 
   local radius = 0 
   local function at_radius(i) 
      local continue = false 
      io.write(string.format("\n\nAt radius     %d:   ", i))
      for n,t in pairs(r) do 
	 if t.d == i 
	 then 
	    continue = true 
	    io.write(string.format("\n  %s, from %s", 
				   gr.name_of_node(g,n),
				   (gr.name_of_node(g,t.pi) or "")))
	 end
      end 
      io.write(string.format("\n\n~~~~\n"))
      return continue
   end

   while at_radius(radius) do radius=radius+1 end
end 
   
function timer() 
   local time = 0 
   return
   function () 
      time = time+1 
      return time 
   end
end 

function dfs(g) 
   local dfs_results = {} 
   local time = timer()  

   -- Fill this in to work by a recursive 
   -- function, without a stack data structure.  

end

function dfs_stack(g) 
   local dfs_results = {} 
   local time = timer() 
   local s = st.new() 

   -- the fn push_new_neighbors goes through the 
   -- neighbors of i and pushes any new neighbors j, 
   -- as indicated by not yet having any dfs_results[j].  
   -- mark the current time and the predecessor i.  

   local function push_new_neighbors (i) 
      for _,e in ipairs(g[i]) do 
	 local j = e.dst
	 if not(dfs_results[j])
	 then 
	    dfs_results[j] = { disc = time(), pi = i } 
	    st.push(s,j)
	 end
      end
   end	 

   -- we walk through the nodes.  
   -- if we havent seen a node before, we push it
   -- and then as long as the stack is non-empty we
   -- push new neighbors 
   -- or else pop off nodes, marking them as finished 

   for i = 1,g.length do 
      if not(dfs_results[i])
      then 
	 dfs_results[i] = { disc = time() , pi = false } 
	 st.push(s,i)
	 while (not(st.empty(s))) do 
	    local i = st.top(s)
	    local t = dfs_results[i]
	    if t.neighbors_done 
	    then 
	       t.fin = time() 
	       st.pop(s) 
	    else
	       push_new_neighbors(i) 
	       t.neighbors_done = true 
	    end
	 end
      end
   end
   return dfs_results 
end

